package Tree;

import sun.reflect.generics.tree.Tree;

import java.util.HashMap;
import java.util.Map;

public class _866_SmallestSubtreewithalltheDeepestNodes {
    Map<TreeNode, Integer> maps = new HashMap<>();
    int deepestLength = 0;
    int nodedeep = 0;
    TreeNode tr;
    boolean sameVal = false;
    public TreeNode subtreeWithAllDeepest(TreeNode root) {
        getDepthLength(root,0);
        nodedeep = deepestLength;
        getNodeDepthLength(root, 0);
        getDepthNode(root,0);
         return tr;
    }

    public void getDepthNode(TreeNode root,int length) {
        if (root != null) {
            int tlength = length + 1;
            if (root.left != null && root.right != null) {
                int ll = maps.get(root.left);
                int rl = maps.get(root.right);
                if (ll == rl && ll + tlength == nodedeep) {
                    tr = root;
                    return ;
                }
                getDepthNode(root.left,tlength);
                getDepthNode(root.right,tlength);
            } else {
                if (tlength == nodedeep) {
                    tr = root;
                }
                getDepthNode(root.left,tlength);
                getDepthNode(root.right,tlength);
            }
        }
    }

    public void getDepthLength(TreeNode root, int length) {
        if (root != null) {
            int tlength = length + 1;
            if (tlength > deepestLength) {
                deepestLength = tlength;
            } else if (tlength == deepestLength) {

            }
            getDepthLength(root.left, tlength);
            getDepthLength(root.right,tlength);
        }
    }

    public void getNodeDepthLength(TreeNode root, int length) {
        if (root != null) {
            deepestLength = 1;
            getDepthLength(root,0);
            maps.put(root,deepestLength);
            deepestLength = 1;
            getNodeDepthLength(root.left,0);
            getNodeDepthLength(root.right,0);
        }
    }

}
